#include <iostream>

using namespace std;

// 枚举所有子字符串 (超时)
bool repeateSubstringPattern(string s) {
    for (int i{}, len = s.size(); i < len - 1; i++) {
        string subStr = s.substr(0, i + 1);
        cout << i << " subStr: " << subStr << "\n";
        string sumStr = subStr;

        while (1) {
            sumStr += subStr;
            cout << "sumStr: " << sumStr << "\n";
            if (sumStr == s) {
                return true;
            } else if (sumStr.size() >= len || sumStr != s.substr(0, sumStr.size())) {
                break;
            }
        }
    }

    return false;
}

// 移位匹配 解法比较巧妙
bool repeateSubstringPattern2(string s) {
    string newStr = s + s;
    return static_cast<int>(newStr.substr(1, newStr.size() - 2).find(s)) >= 0;
}



void getNext(int* next, const string& s) {
    next[0] = 0;
    int j{};
    for (int i = 1; i < s.size(); i++) {
        while (j > 0 && s[i] != s[j]) {
            j = next[j - 1];
        }
        if (s[i] == s[j]) {
            j++;
        }
        next[i] = j;
    }
}
// KMP
// 当一个字符串由重复子串组成的，最长相等前后缀不包含的子串就是最小重复子串

// 如果 len % (len - (next[len - 1])) == 0，next数组没有经过处理，部分匹配表 PMT 数组
// 则说明数组的长度正好可以被 (数组长度-最长相等前后缀的长度) 整除 ，说明该字符串有重复的子字符串。
bool repeateSubstringPattern3(string s) {
    if (s.size() == 0) {
        return false;
    }

    int next[s.size()];
    getNext(next, s);
    int len = s.size();
    if (next[len - 1] != 0 && len % (len - (next[len - 1])) == 0) {
        return true;
    }

    return false;
}



int main() {
    string str { "abaaba" };
    bool result = repeateSubstringPattern3(str);
    cout << "result: " << result << "\n";
    return 0;
}